#include <unordered_map>
#include <unordered_set>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode()
      : val(0), left(nullptr), right(nullptr){} * TreeNode(int x)
      : val(x),
        left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

void compute_path(TreeNode *root, int targetSum, int t, int &path_sum,
                  unordered_set<TreeNode *> &set) {
  if (root == nullptr) {
    return;
  }
  if (set.count(root->left) == 0) {
    compute_path(root->left, targetSum, targetSum, path_sum, set);
    set.insert(root->left);
  }
  if (set.count(root->right) == 0) {
    compute_path(root->right, targetSum, targetSum, path_sum, set);
    set.insert(root->right);
  }
  if (t - root->val == 0) {
    path_sum++;
  }

  compute_path(root->left, targetSum, t - root->val, path_sum, set);
  compute_path(root->right, targetSum, t - root->val, path_sum, set);
}

int pathSum(TreeNode *root, int targetSum) {
  int path_sum = 0;
  unordered_set<TreeNode *> _set;
  compute_path(root, targetSum, targetSum, path_sum, _set);
  return path_sum;
}

// 前缀和解法

void compute_path_(TreeNode *root, int targetSum, int preSum, int &path_sum,
                   unordered_map<int, int> &map) {
  if (root == nullptr) {
    return;
  }
  int x = preSum + root->val - targetSum;
  if (map.count(x) > 0) {
    path_sum++;
  }
  map.count(preSum) == 0 ? map[preSum] = 1 : map[preSum]++;
  compute_path_(root->left, targetSum, preSum + root->val, path_sum, map);
  compute_path_(root->right, targetSum, preSum + root->val, path_sum, map);
  map.count(preSum) == 1 ? map.erase(preSum) : map[preSum]--;
}

int pathSum_(TreeNode *root, int targetSum) {
  int path_sum = 0;
  unordered_map<int, int> preSum_map;
  preSum_map[0] = 1;
  compute_path_(root, targetSum, 0, path_sum, preSum_map);
  return path_sum;
}
